﻿
Imports osi.root.connector
Imports osi.root.constants

'really need to make a circle?
Public Class list(Of valueT)
    Implements linear_container(Of valueT), IComparable(Of list(Of valueT)), IComparable

    Public Class iterator
        Inherits randomAccessIterator(Of node)
        Implements container(Of valueT).iterator

        Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
            If Not [get]() Is Nothing Then
                If prev Then
                    [set]([get]().last())
                Else
                    [set]([get]().next())
                End If

                Return Me <> _end
            Else
                Return False
            End If
        End Function

        Public Sub New()
            MyBase.New()
        End Sub

        Public Sub New(ByVal that As pointer(Of node))
            MyBase.New(that)
        End Sub

        Public Sub New(ByVal that As node)
            MyBase.New(that)
        End Sub

        Public Overloads Shared Operator +(ByVal this As iterator) As valueT
            Return ++cast(Of pointer(Of node))(this)
        End Operator

        Public Overloads Function instance() As valueT Implements container(Of valueT).iterator.instance
            Return MyBase.instance()
        End Function
    End Class

    Public Class node
        Inherits pointernode(Of valueT)

        Private Const _pointerCount As Int64 = 2

        Private Class pointerIndex
            Public Const last As Int64 = 0
            Public Const [next] As Int64 = 1
        End Class

        Public Function last() As node
            Return pointer(pointerIndex.last)
        End Function

        Public Function [next]() As node
            Return pointer(pointerIndex.next)
        End Function

        Public Sub appendlast(ByVal that As node)
            debug_k_assert(Not Object.ReferenceEquals(Me, that), "should not append last to a node itself.")
            pointer(pointerIndex.last) = that
            If Not that Is Nothing Then
                that.pointer(pointerIndex.next) = Me
            End If
        End Sub

        Public Sub appendnext(ByVal that As node)
            debug_k_assert(Not Object.ReferenceEquals(Me, that), "should not append next to a node itself.")
            pointer(pointerIndex.next) = that
            If Not that Is Nothing Then
                that.pointer(pointerIndex.last) = Me
            End If
        End Sub

        Public Sub New()
            MyBase.New(_pointerCount)
        End Sub

        Public Sub New(ByVal newData As valueT)
            MyBase.New(_pointerCount, newData)
        End Sub
    End Class

    Private Shared _end As iterator = Nothing
    Private _front As node
    Private _back As node
    Private _size As Int64

    Public Function begin() As iterator
        Return New iterator(_front)
    End Function

    Public Function container_iterator_begin() As container(Of valueT).iterator _
        Implements linear_container(Of valueT).begin
        Return begin()
    End Function

    Public Function rbegin() As iterator
        Return New iterator(_back)
    End Function

    Public Function container_iterator_rbegin() As container(Of valueT).iterator _
        Implements linear_container(Of valueT).rbegin
        Return rbegin()
    End Function

    Public Function [end]() As iterator
        Return _end
    End Function

    Public Function container_iterator_end() As container(Of valueT).iterator _
        Implements linear_container(Of valueT).end
        Return [end]()
    End Function

    Public Function rend() As iterator
        Return _end
    End Function

    Public Function container_iterator_rend() As container(Of valueT).iterator _
        Implements linear_container(Of valueT).rend
        Return rend()
    End Function

    Public Property front() As valueT Implements linear_container(Of valueT).front
        Get
            Return first()
        End Get
        Set(ByVal value As valueT)
            first() = value
        End Set
    End Property

    Public Property back() As valueT Implements linear_container(Of valueT).back
        Get
            Return last()
        End Get
        Set(ByVal value As valueT)
            last() = value
        End Set
    End Property

    Public Property first() As valueT
        Get
            Return +_front
        End Get
        Set(ByVal value As valueT)
            If Not empty() Then
                _front.data = value
            End If
        End Set
    End Property

    Public Property last() As valueT
        Get
            Return +_back
        End Get
        Set(ByVal value As valueT)
            If Not empty() Then
                _back.data = value
            End If
        End Set
    End Property

    Private Function find(ByVal index As Int64) As node
        Dim rtn As node = Nothing
        If Not availableIndex(index) Then
            rtn = Nothing
        Else
            If index <= _size \ 2 Then
                rtn = _front
                While index > 0
                    rtn = rtn.next
                    index -= 1
                End While
            Else
                rtn = _back
                index = _size - index - 1
                While index > 0
                    rtn = rtn.last
                    index -= 1
                End While
            End If
        End If

        Return rtn
    End Function

    Public Function [goto](ByVal index As Int64) As iterator
        Return New iterator(find(index))
    End Function

    Public Function find(ByVal v As valueT) As iterator
        Dim it As iterator = Nothing
        it = begin()
        While it <> [end]()
            If compare(v, +it) = 0 Then
                Return it
            End If

            it += 1
        End While

        Return [end]()
    End Function

    Public Function rfind(ByVal v As valueT) As iterator
        Dim it As iterator = Nothing
        it = rbegin()
        While it <> rend()
            If compare(v, +it) = 0 Then
                Return it
            End If

            it -= 1
        End While

        Return rend()
    End Function

    Public Function availableIndex(ByVal index As Int64) As Boolean
        Return index >= 0 And index < size()
    End Function

    Public Function size() As Int64 Implements linear_container(Of valueT).size
        Return _size
    End Function

    Default Public Property at(ByVal index As Int64) As valueT Implements linear_container(Of valueT).at
        Get
            Dim rtn As node = Nothing
            rtn = find(index)
            Return +rtn
        End Get
        Set(ByVal value As valueT)
            Dim rtn As node = Nothing
            rtn = find(index)
            If Not rtn Is Nothing Then
                rtn.data = value
            End If
        End Set
    End Property

    Public Function empty() As Boolean Implements linear_container(Of valueT).empty
        Return size() = 0
    End Function

    Public Function push_back(ByVal newData As valueT) As Boolean Implements linear_container(Of valueT).push_back
        Dim add As node = Nothing
        add = New node(newData)
        If Not _back Is Nothing Then
            _back.appendnext(add)
        Else
            _front = add
        End If
        _back = add
        _size += 1

        Return True
    End Function

    Public Function push_front(ByVal newData As valueT) As Boolean Implements linear_container(Of valueT).push_front
        Dim add As node = Nothing
        add = New node(newData)
        If Not _front Is Nothing Then
            _front.appendlast(add)
        Else
            _back = add
        End If
        _front = add
        _size += 1

        Return True
    End Function

    Public Function pop_back() As Boolean Implements linear_container(Of valueT).pop_back
        If empty() Then
            Return False
        Else
            [erase](_back)
            Return True
        End If
    End Function

    Public Function pop_front() As Boolean Implements linear_container(Of valueT).pop_front
        If empty() Then
            Return False
        Else
            [erase](_front)
            Return True
        End If
    End Function

    Public Function insert(ByVal it As iterator, ByVal newdata As valueT) As iterator
        Return insert(+cast(Of pointer(Of node))(it), newdata)
    End Function

    Private Function insert(ByVal it As node, ByVal newData As valueT) As iterator
        Dim work As node = Nothing
        If it Is Nothing Then
            Return [end]()
        Else
            work = New node(newData)
            'it.next will be changed after work.appendlast(it)
            work.appendnext(it.next)
            work.appendlast(it)
            If Object.ReferenceEquals(it, _back) Then
                _back = work
            End If
            _size += 1
            it = it.next()
            debug_k_assert(Not it Is Nothing, "it.next() is nothing after insert.")

            Return New iterator(it)
        End If
    End Function

    Public Function insert(ByVal index As Int64, ByVal newData As valueT) As iterator
        Return insert(find(index), newData)
    End Function

    Public Function insert(ByVal newData As valueT) As container(Of valueT).iterator _
                                                                            Implements container(Of valueT).insert
        push_back(newData)
        Return rbegin()
    End Function

    Private Function [erase](ByVal it As node) As iterator
        If it Is Nothing Then
            Return [end]()
        Else
            Dim del As node = it
            If Not it.last Is Nothing Then
                it.last.appendnext(it.next)
            ElseIf Not it.next Is Nothing Then
                it.next.appendlast(it.last)
            End If
            If Object.ReferenceEquals(it, _front) Then
                _front = it.next
            End If
            If Object.ReferenceEquals(it, _back) Then
                _back = it.last
            End If
            If Not it Is Nothing Then
                it = it.next
            Else
                it = Nothing
            End If
            _size -= 1
            del.appendlast(Nothing)
            del.appendnext(Nothing)
            Return New iterator(it)
        End If
    End Function

    Public Function [erase](ByVal it As iterator) As iterator
        Return [erase](+cast(Of pointer(Of node))(it))
    End Function

    Public Function [erase](ByVal index As Int64) As iterator
        Return [erase](find(index))
    End Function

    Public Function [erase](ByVal s As valueT) As iterator
        Return [erase](find(s))
    End Function

    Public Sub clear() Implements linear_container(Of valueT).clear
        _front = Nothing
        _back = Nothing
        _size = 0
    End Sub

    Public Function Clone() As Object Implements linear_container(Of valueT).Clone
        Dim rtn As list(Of valueT) = Nothing
        Dim it As list(Of valueT).node
        rtn = alloc(Me)
        it = _front
        While Not it Is Nothing
            rtn.push_back(it.data)
            it = it.next
        End While

        Return rtn
    End Function

    Shared Sub New()
        _end = New iterator(cast(Of node)(Nothing))
    End Sub

    Public Sub New()
        clear()
    End Sub

    Public Function contains(ByVal v As valueT) As Boolean
        Return find(v) <> [end]()
    End Function

    Public Function CompareTo(ByVal that As list(Of valueT)) As Int32 _
                                                                Implements IComparable(Of list(Of valueT)).CompareTo
        k_assert(Not that Is Nothing, "that should not be nothing after inherits from IComparable2.")

        Dim i As list(Of valueT).iterator = Nothing
        Dim j As list(Of valueT).iterator = Nothing

        i = begin()
        j = that.begin()
        While i <> [end]() AndAlso j <> that.end()
            Dim cmp As Int32
            cmp = compare(+cast(Of pointer(Of node))(i), +cast(Of pointer(Of node))(j))
            If cmp <> 0 Then
                Return cmp
            End If

            i += 1
            j += 1
        End While

        If i = [end]() AndAlso j = that.end() Then
            Return 0
        ElseIf i = [end]() Then
            Return -1
        Else
            Return 1
        End If
    End Function

    Public Function CompareTo(ByVal that As Object) As Int32 Implements IComparable.CompareTo
        Return CompareTo(cast(Of list(Of valueT))(that, False))
    End Function

    Public Shared Operator =(ByVal this As list(Of valueT), ByVal that As list(Of valueT)) As Boolean
        Return operatorEqual(this, that)
    End Operator

    Public Shared Operator <>(ByVal this As list(Of valueT), ByVal that As list(Of valueT)) As Boolean
        Return operatorUnequal(this, that)
    End Operator

    Public Shared Operator =(ByVal this As list(Of valueT), ByVal that As Object) As Boolean
        Return operatorEqual(this, that)
    End Operator

    Public Shared Operator <>(ByVal this As list(Of valueT), ByVal that As Object) As Boolean
        Return operatorUnequal(this, that)
    End Operator

    Public Shared Function emptyToString(ByVal it As randomAccessIterator(Of node)) As String
        Return Convert.ToString(++it)
    End Function

    Public Overloads Function ToString(ByVal startIndex As Int64,
                                       ByVal f As Func(Of randomAccessIterator(Of node), String),
                                       Optional ByVal seperator As String = character.tab) As String
        Return operators.ToString(Of node, iterator)(f, [goto](startIndex), [end](), seperator)
    End Function

    Public Overloads Function ToString(ByVal f As Func(Of randomAccessIterator(Of node), String),
                                       Optional ByVal seperator As String = character.tab) As String
        Return operators.ToString(Of node, iterator)(f, begin(), [end](), seperator)
    End Function

    Public Overloads Function ToString(ByVal startIndex As Int64, _
                                       Optional ByVal seperator As String = character.tab) As String
        Return ToString(startIndex, AddressOf emptyToString, seperator)
    End Function

    Public Overloads Function ToString(ByVal seperator As String) As String
        Return ToString(AddressOf emptyToString, seperator)
    End Function

    Public Overrides Function ToString() As String
        Return ToString(character.tab)
    End Function
End Class
